import java.util.Comparator;

/**
 * This is an implementation of a heap that is backed by an array.
 * 
 * This implementation will accept a comparator object that can be used to
 * define an ordering of the items contained in this heap, other than the
 * objects' default compareTo method (if they are comparable). This is useful if
 * you wanted to sort strings by their length rather than their lexicographic
 * ordering. That's just one example.
 * 
 * Null should be treated as positive infinity if no comparator is provided. If
 * a comparator is provided, you should let it handle nulls, which means it
 * could possibly throw a NullPointerException, which in this case would be
 * fine.
 * 
 * If a comparator is provided that should always be what you use to compare
 * objects. If no comparator is provided you may assume the objects are
 * Comparable and cast them to type Comparable<T> for comparisons. If they
 * happen to not be Comparable you do not need to handle anything, and you can
 * just let your cast throw a ClassCastException.
 * 
 * This is a minimum heap, so the smallest item should always be at the root.
 * 
 * @param <T>
 *            The type of objects in this heap
 */
public class BinaryHeap<T> implements Heap<T> {

	/**
	 * The comparator that should be used to order the elements in this heap
	 */
	private Comparator<T> comp;

	/**
	 * The backing array of this heap
	 */
	private T[] data;

	/**
	 * The number of elements that have been added to this heap, this is NOT the
	 * same as data.length
	 */
	private int size;

	/**
	 * Default constructor, this should initialize data to a default size (11 is
	 * normally a good choice)
	 * 
	 * This assumes that the generic objects are Comparable, you will need to
	 * cast them when comparing since there are no bounds on the generic
	 * parameter
	 */
	public BinaryHeap() {
		data = (T[])(new Comparable[11]);
		comp = null;
		
	}

	/**
	 * Constructor that accepts a comparator to use with this heap. Also
	 * initializes data to a default size.
	 * 
	 * When a comparator is provided it should be preferred over the objects'
	 * compareTo method
	 * 
	 * If the comparator given is null you should attempt to cast the objects to
	 * Comparable as if a comparator were not given
	 * 
	 * @param comp
	 */
	public BinaryHeap(Comparator<T> comp) {
		data = (T[]) new Comparable[11];
		this.comp = comp;
	}

	@Override
	public void add(T item) {
		if (size + 1 >= data.length) {
			resize();
		}

		size++;
		data[size] = item;

		bubbleUp(size);
	}
	
	private void resize() {
		int newSize = (2 * data.length) + 1;

		T[] oldData = data;
		T[] newData = (T[])new Comparable[newSize];

		transferData(oldData, newData);

		data = newData;
	}
	
	private void transferData(T[] oldData, T[] newData) {
		int i = 0;
		for (int j = 0; j < oldData.length; j++) {
			T entry = oldData[j];
			if (entry != null) {
				oldData[j] = null;
				newData[i] = entry;
				i++;
			}
		}
	}
	
	private void bubbleUp(int index) {
		while ((index > 1) && (compare(data[parent(index)], data[index]) > 0)) {
			T temp = data[index];
            data[index] = data[parent(index)];
            data[parent(index)] = temp;
            index = parent(index);
		}
	}
	
	private int compare(T data1, T data2) {
		if (comp != null) {
			return comp.compare(data1,  data2);
		} 
		
		else {
			if (data1 != null && data2 != null) {
				return ((Comparable<T>)data1).compareTo(data2);
			} 
			
			else if (data1 == null) {
				return 1;
			} 
			
			else if (data2 == null) {
				return -1;
			} 
			
			else {
				return 0;
			}
		}
	}
	
	private int parent(int index) {
		return index / 2;
	}

	@Override
	public boolean isEmpty() {
		return (size == 0);
	}

	@Override
	public T peek() {
		if (isEmpty()) {
			return null;
		}
		return data[1];
	}

	@Override
	public T remove() {
		if (size == 0) {
			return null;
		}
		T value = peek();
		data[1] = data[size];
		data[size] = null;
		size--;
		bubbleDown(1);

		return value;
	}
	
	private void bubbleDown(int index) {
		if (size <= 1) {
			return;
		}

		int leftIndex = leftChild(index);
		int rightIndex = rightChild(index);

		while (leftIndex != -1 || rightIndex != -1) {
			T left = (leftIndex == -1) ? null : data[leftIndex];
			T right = (rightIndex == -1) ? null : data[rightIndex];

			int minIndex = left == null ? rightIndex : leftIndex;
			if (right != null && left != null) {
				minIndex = (compare(left, right) < 0) ? leftIndex : rightIndex;
			}

			if (compare(data[index], data[minIndex]) > 0) {
                T temp = data[index];
                data[index] = data[minIndex];
                data[minIndex] = temp;
            }
			
			else {
                break;
            }

			index = minIndex;
			rightIndex = rightChild(index);
			leftIndex = leftChild(index);
		}
	}
	
	private int leftChild(int index) {
		int child = (index * 2);
		if (child > size) return -1;
		return child;
	}
	
	private int rightChild(int index) {
		int child = (index * 2) + 1;
		if (child > size) return -1;
		return child;
	}

	@Override
	public int size() {
		return size;
	}
}